package com.gitee.alg.sort


/**
 * Project Name: alg
 * Des: 直接插入排序
 * Package:com.gitee.alg.sort
 * @author Arlo Sun
 * @date 2021/4/26 - 13:03
 */
class InsertionSort<T : Comparable<T>>(override val compare: (T, T) -> Boolean) : ArraySort<T> {


    override fun sort(array: Array<T>, ascend: Boolean): Array<T> {

        //从第二个元素开始，找到插入位置
        for (i in 1 until array.size) {
            //待插入的数据
            val pointer = array[i]
            var j = i
            //循环条件是前面还有元素 pointer比前面的元素大
            //compare(array[j - 1], pointer)  => array[j - 1] > pointer
            while (j > 0 && compare(array[j - 1], pointer)) {
                array[j] = array[j - 1]
                j--
            }
            if (j != i) {
                array[j] = pointer
            }
        }

        return array
    }
}